package org.neptune.common.sort;

import java.util.Arrays;

/** 希尔排序 */
public class ShellSort {

	/**
	 * Shellsort是最古老的排序算法之一，该算法以其发明者Donald L. Shell的名字命名（1959）。
	 * 在ShellSort排序算法之前的算法时间复杂度基本都是O(n2)O(n2)，该算法是突破这个时间复杂度的第一批算法之一。 另外 Shellsort
	 * 是快速、易于理解和易于实现的。 然而，其复杂度分析有点复杂。
	 */
	public static void main(String[] args) {
		int[] list = { 27, 76, 47, 23, 7, 32, 19, 86 };
		System.out.println("************希尔排序************");
		System.out.println("排序前：");
		display(list);
		System.out.println("");

		System.out.println("排序后：");
		shellSort(list);
		display(list);
	}

	/** 希尔排序算法 */
	public static void shellSort(int[] list) {
		int len = list.length;
		// 取增量
		int gap = len / 2;

		while (gap >= 1){
			// 无序序列
			for (int i = gap; i < len; i++){
				int temp = list[i];
				int j;

				// 有序序列
				for (j = i - gap; j >= 0 && list[j] > temp; j = j - gap){
					list[j + gap] = list[j];
				}
				list[j + gap] = temp;
			}

			// 缩小增量
			gap = gap / 2;
		}
	}

	public static void shellSort1(int[] arr) {
		if (arr == null){
			return;
		}
		int len = arr.length;// 数组的长度
		int k = len / 2;// 初始的增量为数组长度的一半
		// while循环控制按增量的值来划不同分子序列，每完成一次增量就减少为原来的一半
		// 增量的最小值为1，即最后一次对整个数组做直接插入排序
		while (k > 0){
			// 里边其实就是升级版的直接插入排序了，是对每一个子序列进行直接插入排序，
			// 所以直接将直接插入排序中的‘1’变为‘k’就可以了。
			for (int i = k; i < len; i++){
				int j = i;
				int target = arr[i];
				while (j >= k && target < arr[j - k]){
					arr[j] = arr[j - k];
					j -= k;
				}
				arr[j] = target;
			}
			// 不同增量排序后的结果
			System.out.println("增量为" + k + "排序之后：" + Arrays.toString(arr));
			k /= 2;
		}
	}

	/** 遍历打印 */
	public static void display(int[] list) {
		if (list != null && list.length > 0){
			for (int num : list){
				System.out.print(num + " ");
			}
			System.out.println("");
		}
	}
}
